package wtx.geeks;

import java.util.List;
import java.util.ArrayList;

/**
 * https://practice.geeksforgeeks.org/problems/geek-collects-the-balls/0
 */
public final class GeekCollectBalls {
  public int maxBallCoins(int[] path1, int[] path2) {
    List<int[]> joinList = new ArrayList<>();
    final int N1 = path1.length;
    final int N2 = path2.length;
    for (int i = 0, j = 0; i < N1 && j < N2; ) {
      if (path1[i] > path2[j]) {
        ++j;
      } else if (path1[i] < path2[j]) {
        ++i;
      } else {
        int[] e = {i, j};
        joinList.add(e);
        int i0 = i, j0 = j; 
        while(++i < N1 && path1[i] == path2[j0]);
        while(++j < N2 && path1[i0] == path2[j]);
        if (j - 1 > j0) {
          int[] e1 = { i0, j - 1 };
          joinList.add(e1);
        }
        if (i - 1 > i0) {
          int[] e2 = { i - 1, j0 };
          joinList.add(e2);
        }
      }
    } 
    int[] endPoint = {N1, N2};
    joinList.add(endPoint);
    int[] scores = {0, 0};
    final int joinCnt = joinList.size();
    int[] joinPos = {0, 0};
    for (int i = 0; i < joinCnt; ++i) {
      int[] nextJoin = joinList.get(i);
      int maxLast = Math.max(scores[0], scores[1]);
      int sumR = sumRange(path1, joinPos[0], nextJoin[0]);
      scores[0] = maxLast + sumR;
      sumR = sumRange(path2, joinPos[1], nextJoin[1]);
      scores[1] = maxLast + sumR;
      joinPos = nextJoin;
    }
    return Math.max(scores[0], scores[1]);
  }


  private static int sumRange(int[] arr, int start, int end) {
    int sum = 0;
    for (int i = start; i < end; ++i) {
      sum += arr[i];
      arr[i] = 0;
    }
    return sum;
  }
  /**
   * Says hello to the world.
   * 
   * @param args
   *               The arguments of the program.
   */
  public static void main(String[] args) {
    int[] path1 = {1, 4, 5, 6, 8}, path2 = {2, 3, 4, 6, 9};
    GeekCollectBalls solution = new GeekCollectBalls();
    System.out.println(solution.maxBallCoins(path1, path2));
  }
}
